COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.SS ANALYST
C00023 ENDMK
C⊗;
.SS ANALYST

ANALYST scans a computerized "intelligence" data base.
It looks for
patterns of information that suggest conjectures about an adversary's
capabilities, intentions, knowledge, beliefs and goals.  When ANALYST
thinks it has found something significant, it informs a human analyst
about its conclusions (and if requested about how it reached them).  Its
forte is examining more data than is possible for a human and guaranteeing
that all possibilities of the kinds it is programmed for are pursued.  The
example is somewhat contrived, because we have emphasized the problems we
are currently studying and ignored others.  Moreover, the ANALYST we plan
to program will be quite
limited in its capabilities, partly because we have only partially solved
the problems we are studying, but mainly because of problems no-one has
begun to study.

Suppose ANALYST reads in a report from Damascus:
.begin indent 2,2

%2Major Alexei Ivanov went to Damascus airport, bought a ticket to Moscow
for cash, and departed on the next flight to Moscow%1.
.end

ANALYST asks itself why Ivanov did what he did.  Usually it finds
hypotheses that fit a normal pattern of behavior and gains nothing but
further defining the normal pattern.  Let's suppose there is more in this
case.

%2Why did he pay cash%1?  This question arises from a program that looks
for motives of actions that are found to deviate
from a normal pattern.  We suppose that the data base
contains a statement that Russians usually buy tickets from their travel
agency Intourist.  The conjecture is then formed that Ivanov is in a hurry
and that some event has required him to go to Moscow suddenly.  The
hypothesis is confirmed by discovering that he had previously accepted an
invitation incompatible with a Moscow trip.

Now suppose that it is known or conjectured that Ivanov is a radar expert.
This leads ANALYST to scan facts about our adversary relationship with the
Russians in the field of radar including the fact that we are trying to
find out the pattern of frequency variation of their radars.  One general
fact in the data base is that when one side finds out the frequency
variation pattern of a radar, the other side wants to change it.
%2Therefore, analyst conjectures that the Russians think we will soon know
the frequency variation pattern of their R111 radar%*.

This simple example poses several problems not handled by present database
programs.  First, present data base systems store particular facts, not
general facts.  General facts usually have to be built into programs or at
least into productions.  Second, the laws that determine what conclusions
can be drawn from facts about knowledge, belief and intentions are
different from those governing non-mental qualities, and present programs
don't use the laws that apply to these %2modal%1 concepts.  Third, the
reasoning required even to conjecture that Ivanov is in a hurry involves
conjecturing that his behavior is normal except in so far as specific
facts suggest abnormalities.  Fourth, many reasoning processes involve
observation as well as reasoning from facts in a data base.  Obtaining the
confirming evidence that Ivanov is in a hurry has that character.
Finally, the pattern recognition required to conjecture from Ivanov's
hurried Moscow trip and the previously known facts that they think we will
soon know their radar pattern is quite different from that done today.  We
shall consider these problems in turn.

.CB Representing general facts

Few existing data base systems represent general facts by entries in the
data base.  For example, ANALYST needs to represent the fact that the
Russians almost always buy their airline tickets from Intourist in such a
way that further deductions can be made and the fact can be modified by
new evidence.  Existing systems represent them by program or by
%2semi-programs%1 like productions.  This works very well for applying the
general facts to particular cases, but it doesn't work well for deducing
new general facts from old ones or representing facts about facts.  In
order to represent general assertions, e.g. Russians buy their tickets
from Intourist, one needs quantifiers, and the most developed logical
system with quantifiers is first order logic.  Even within first order
logic, there are many possible ways of representing a particular kind of
fact, and much further study is required.

.CB Knowledge and belief

The notion %2X thinks Y will soon know Z%1 is not unusually complex when
adversaries try to outwit each other.  It presents problems for machine
fepresentation that haven't been conclusively solved but on which we have
made recent progress.

In order to be useful ANALYST must do more than just represent the above
fact.  It must be able to prove or conjecture it under appropriate
circumstances and it must be able to draw correct conclusions from it -
and not draw incorrect conclusions.  The latter is the more immediate
problem.  Let us use a simpler example.  Suppose we have the sentences
%2Pat knows Mike's telephone number%1 and %2Mike's telephone number is the
same as Mary's%1.  A computerized deduction system that uses the rule that
equals may be substituted for equals might conclude %2Pat knows Mary's
telephone number%1.  This is not a legitimate deduction, even though it
would be legitimate to deduce that Pat dialed Mary's telephone number from
the fact that he dialed Mike's number and the fact that the numbers are
the same.

The fact that substitution of equals for equals is legitimate in some
contexts and not in others has been well known for a very long time.
Correct logical laws for handling such cases have been proposed, but the
presently known solutions have two defects.  First they usually treat only
one such function at a time such as "knows" while real life problems often
mix up several even in the same sentence, e.g. think and know - %2They
think we will soon know ...%1.  Second, each such mental quality requires
modifying the logic.  In a practical case this would be many months work
and might have to be done again and again.

Recently McCarthy has discovered how to represent such facts in unmodified
first order logic.  An improved and extended version of this method
developed by Creary permits the adequate representation of statements
involving any number of different propositional attitudes, nested to any
depth.  The work is described in [McCarthy 1978e] and [Creary 1979], and
will be further developed in the next year.

.CB Conjectures

It has long been recognized that standard logic does not represent the
many kinds of reasoning that people use in forming conjectures.  It now
appears that much human reasoning involves conjecturing that the known
facts about a phenomenon are all the relevant facts.  Thus ANALYST must
conjecture that Ivanov was in a hurry because it has no other explanation
even though it cannot conclusively exclude other explanations.

Strict logical deduction does not permit drawing a conclusion from certain
facts that would be changed if additional facts, supplementing but not
contradicting them, were discovered.  In logic, if a conclusion follows,
it will still follow when more facts are added.  Humans, on the other
hand, are always drawing this kind of conclusion.  We now think that
machines must also reason this way, and that programs confined to strict
logical reasoning must either be unable to draw conclusions or they must
use axioms so unqualified that they are false.

There are two parts to the problem of drawing such tentative conclusions.
The first part is that of deciding what assumptions to make to facilitate
one's reasoning, and the second part is that of actually making those
assumptions.  The first of these problems is difficult in novel situations,
for one just knows one lacks information, without being sure exactly what
one should know.  However, in routine situations, one has already considered
or been told what are the reasonable assumptions to make, and these can
simply be stated as general, rule-of-thumb facts, that is, rules which
tolerate exceptions.  Partial solutions to both of these problems have
been found: to the first, a technique called circumscription, and to the
second, techniques called default rules and reason maintenance.

McCarthy has proposed circumscription
as a partial solution to the problem of constructing assumptions[McCarthy
1978d].  An axiom schema of first order logic called the %2circumscription
induction schema%1 can be used to represent in a flexible way the
conjecture that the entities that can be shown to exist on the basis of
the information in a certain data base are all the relevant entities that
exist.  The flexibility comes from the fact that the set of information
conjectured to be all the relevant information is readily changed.  Martin
Davis of New York University has helped in the mathematical formulation of
circumscription.

Circumscription is a fully formal mode of reasoning and can be programmed
for a computer.  On the other hand, it is not %2valid%1, i.e.  it can yield
false conclusions from true premises.  This is to be expected, because
mathematicians have proved the completeness of the rules of inference of
first order logic; hence all the infallible inferences that do not depend
on the interpretation of the premises and/or conclusion have already been
provided for.  So, programs that use circumscription cannot be certain
that their conclusions are as good as their premises, and must be made
capable of withdrawing conclusions arrived at by circumscription that turn
out to be unacceptable, without necessarily also renouncing the premises.
This will make them more like humans - getting increased power at the
price of fallibility.

The problem of making routine assumptions has been approached in many
ways in artificial intelligence programs, perhaps the most common being
the technique of default fillers of frame slots.  These techniques all
had serious problems, though, as they did not interpret the statements of
these defaults carefully enough to ensure sensible behavior.  Recently
Jon Doyle proposed reason maintenance systems a first solution to this
problem [Doyle 1979, 1980].  Reason maintenance systems record the
inferences made by a reasoner, and examine the set of reasons to decide
on a coherent set of assumptions to adopt.  Routine assumptions appear
in this framework as default rules, such as "All birds fly," which are
used to construct non-monotonic justifications, records of non-monotonic
inferences.  In addition to their importance in making assumptions,
reason maintenance systems are instrumental in many other necessary functions
of reasoning programs, including database updates, explanation of database
entries, and, as explained next, decision-making.

.cb Decision-Making

A key problem for any agent carrying out complex activities or solving
difficult problems is that of making decisions.  For example, ANALYST must
make decisions about which possible interpretation to take of each new
fact learned, and must also make further decisions about how to fit these
individual decisions into global interpretations of what is going on.
Subjective Bayesian decision theory is perhaps the best developed formal
theory of making decisions, but proves overly restrictive in its requirement
of complete information about actions, consequences, and utilities.  Recently
Jon Doyle has developed a new technique for decision-making called reasoned
deliberation [Doyle 1980].  Reasoned deliberation views the decision-making
process as a reasoning task itself.  It involves incremental construction,
by means of general rules of thumb about decision-making, of the various
possible actions, their expected consequences, and the partial preferences
and utilites (when known) among them.  It applies these general rules in
a pattern of dialectical argumentation, in which one rule will construct
a reason for acting on one option, a second rule will challenge that reason,
a third rule will challenge the challenging reason, and so on.  These general
rules are important in succinctly specifying special cases and exceptions to
other general rules.  This technique makes important use of the maintenance
and explanation facilities provided by reason maintenance techniques.

.CB Patterns

Many of the patterns ANALYST will have to recognize do not fall into the
categories so far treated in AI work.  For example, explaining an unknown
activity of an adversary requires conjecturing a goal and its relation to
other goals, a belief structure that makes the goal seem desirable and
attainable, and a means of attaining the goal that gives rise to the
observations.  Present AI pattern recognition programs find patterns in
observed data rather than introduce new entities in order to explain the
data.  McCarthy is developing a general notion of pattern.  Wilkins's thesis
used chess to develop some advanced notions of strategic pattern.